#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,maxn=1e5+5;
int n,T,v1[maxn],v2[maxn],v3[maxn],ans;
string s,t,x,p;
int read(){
    int s=0;
    char ch=getchar(),last=' ';
    while(ch<'0'||ch>'9')
        last=ch,ch=getchar();
    while(ch>='0'&&ch<='9')
        s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return last=='-'?-s:s;
}
signed main(){
    freopen("brotherhood.in","r",stdin);
    freopen("brotherhood.out","w",stdout);
    n=read(),T=read();
    if(n>10){
        v1[1]=1;
        v2[2]=1;
        for(int i=3;i<=n;i++){
            v1[i]=v1[i-1]+v1[i-2];
            v2[i]=v2[i-1]+v2[i-2];
            v3[i]=v3[i-1]+v3[i-2];
            if(v1[i]>=mod)
                v1[i]-=mod;
            if(v2[i]>=mod)
                v2[i]-=mod;
            if(v3[i]>=mod)
                v3[i]-=mod;
            if(i%2&&i>3)
                ++v3[i];
            if(v3[i]>=mod)
                v3[i]-=mod;
        }
        while(T--){
            cin>>p;
            int l=p.size();
            if(p[0]=='0'&&l==1){
                printf("%lld\n",v1[n]);
                continue;
            }
            if(p[0]=='1'&&l==1){
                printf("%lld\n",v2[n]);
                continue;
            }
            if(p[0]=='1'&&l==2){
                printf("%lld\n",v3[n]);
                continue;
            }
            puts("0");
        }
        return 0;
    }
    s='0',t='1';
    if(n==1)
        x=s;
    if(n==2)
        x=t;
    for(int i=3;i<=n;i++){
        x=t+s;
        s=t,t=x;
    }
    int L=x.size();
    while(T--){
        ans=0;
        cin>>p;
        int l=p.size();
        for(int i=0;i<L&&i+l-1<L;i++)
            for(int j=0;j<l;j++){
                if(x[i+j]!=p[j])
                    break;
                if(j==l-1)
                    ans++;
            }
        printf("%lld\n",ans);
    }
    return 0;
}